package code.commonAlgorithm;

import utils.ListNode;

/**
 * @author 26029
 * @date 2025/4/16
 * @description
 */
public class MergeSort {
    // 链表的归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        // 根据快慢指针找到中间位置
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        // 归并排序递归左面和右面
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        // 合并
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

    // 主函数：递归地拆分数组并排序
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return; // 终止条件：只有一个元素

        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);      // 对左边排序
        mergeSort(arr, mid + 1, right); // 对右边排序
        merge(arr, left, mid, right);   // 合并两个有序区间
    }

    // 合并两个有序子数组
    private static void merge(int[] arr, int left, int mid, int right) {
        // 创建临时数组保存合并结果
        int[] temp = new int[right - left + 1];

        int i = left;     // 左侧起点
        int j = mid + 1;  // 右侧起点
        int k = 0;        // 临时数组索引

        // 比较左右数组的元素，小的先放进temp
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 把左侧剩余元素放入temp
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 把右侧剩余元素放入temp
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 把排序结果复制回原数组
        for (int t = 0; t < temp.length; t++) {
            arr[left + t] = temp[t];
        }
    }

    // 主程序：测试归并排序
    public static void main(String[] args) {
        int[] arr = {8, 3, 1, 7, 2, 5, 4, 6};
        System.out.println("排序前：");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1); // 开始归并排序

        System.out.println("排序后：");
        printArray(arr);
    }

    // 打印数组工具函数
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
